W3. Конечные автоматы (FSA), формальные определения, распознавание языков
1. Краткое содержание
1.1 Историческая справка
Теория конечных автоматов сложилась в 1940–1960‑е годы благодаря работам нескольких исследователей:
- Уоррен Маккаллок и Уолтер Питтс (1943): опубликовали первую математическую модель нейронной сети, используя структуры, близкие к конечным автоматам; показали, что нейроны, выполняющие логические операции, можно моделировать как конечные автоматы.
- Стивен Клини (1951): формализовал регулярные события и доказал эквивалентность конечных автоматов и регулярных выражений, заложив алгебраический фундамент теории.
- Эдвард Ф. Мур (1956): ввёл машину Moore — преобразователь, выход которого зависит только от текущего состояния.
- Джордж Х. Мили (1955): ввёл машину Mealy — преобразователь, выход которого зависит и от текущего состояния, и от текущего входного символа.
- Майкл О. Рабин и Дана Скотт (1959): опубликовали статью «Finite Automata and Their Decision Problems», ввели недетерминированные конечные автоматы (NFA) и доказали их эквивалентность детерминированным. За эту работу им присудили премию Тьюринга в 1976 году.
Эти результаты закрепили роль FSA как центральной модели в теоретической информатике, конструировании компиляторов и теории формальных языков.
1.2 FSA и машина Тьюринга
Машина Тьюринга — существенно более мощная модель вычислений: у неё есть бесконечная лента как неограниченная память, поэтому она может решать задачи, недоступные FSA. Однако эта общность имеет практическую цену:
- FSA обладают лишь конечной памятью (текущее состояние кодирует всю доступную информацию). Они просты, быстры и удобны для распознавания шаблонов в потоках данных.
- Машины Тьюринга в принципе требуют бесконечной памяти, что нереализуемо в физическом оборудовании.
Для многих инженерных задач — лексический анализ, проверка протоколов, аппаратные контроллеры, фильтрация сетевых пакетов — распознаваемые шаблоны регулярны: не нужно считать до произвольной глубины или помнить неограниченную историю. FSA достаточно и гораздо эффективнее. Неограниченная мощность машины Тьюринга для таких задач излишня и лишь усложняет решение.
Ключевой принцип: используйте простейшую модель вычислений, достаточную для задачи. Для регулярных шаблонов уместны FSA.
1.3 Что такое конечный автомат?
FSA (Finite State Automaton) — математическая модель вычислений для распознавания шаблонов и обработки последовательностей символов; ту же модель в узком смысле называют также FSM (Finite State Machine). Это одна из простейших и при этом очень важных моделей. FSA — абстрактная машина, которая:
- Начинает работу в выделенном start state — начальном состоянии.
- Читает входные символы по одному из alphabet \(\Sigma\) — конечного множества допустимых символов.
- Совершает transitions между states в зависимости от входного символа и текущего состояния.
- Даёт ответ Accept или Reject в зависимости от того, оказались ли мы в accepting (final) state — принимающем состоянии.
Можно думать об FSA как об очень простом компьютере с фиксированным объёмом памяти — ровно настолько, чтобы помнить, в каком из конечного числа состояний он сейчас находится. Произвольную информацию он хранить не может, но может распознавать шаблоны, задаваемые регулярными правилами.
1.4 Примеры из практики
FSA повсюду в информатике:
- Торговые автоматы: состояния соответствуют внесённой сумме; каждая монета переводит в новое состояние.
- Светофоры: состояния — красный, жёлтый, зелёный; переходы задаются временем или датчиками.
- Лексические анализаторы (lexer): в компиляторах FSA выделяют лексемы — идентификаторы, ключевые слова, числа в исходном коде.
- Персонажи в играх: поведение вроде «блуждание», «преследование», «бегство» — состояния с переходами по событиям.
- Разбор текста: распознавание шаблонов в документах.
- Анализ протоколов: проверка допустимости последовательностей сетевых сообщений.
1.5 Неформальное введение с примерами
Пример: турникет (вход в метро)
Представьте турникет:
- Состояния: Заперто (пройти нельзя) и Открыто (можно пройти)
- Начальное состояние: Заперто
- Принимающее состояние: Заперто (система в корректном состоянии)
- Алфавит: {Толкнуть, Монета}
- Переходы:
- Из Заперто: Монета → Открыто; Толкнуть → остаёмся в Заперто.
- Из Открыто: Толкнуть → Заперто (прошли и снова заперли); Монета → остаёмся в Открыто.
Этот простой FSA полностью описывает поведение турникета.
1.6 Формальное определение конечного автомата
Детерминированный конечный автомат (DFA) формально задаётся как 5‑ка:
\[M = (Q, \Sigma, \delta, q_0, F)\]
где:
- \(Q\): конечное множество состояний. Пример: \(Q = \{\text{Заперто}, \text{Открыто}\}\) или \(Q = \{q_0, q_1, q_2, q_3, q_4\}\)
- \(\Sigma\): конечное множество входных символов, называемое алфавитом. Пример: \(\Sigma = \{0, 1\}\) (двоичный) или \(\Sigma = \{a, b, c\}\)
- \(\delta\): функция переходов, задающая перемещение между состояниями. Это функция \(\delta: Q \times \Sigma \rightarrow Q\): по паре «состояние \(q\)» и «символ \(\sigma\)» указывается следующее состояние. Если \(\delta\) определена для всех пар \((q, \sigma)\), FSA называют полным; иначе — неполным.
- \(q_0\): начальное состояние, \(q_0 \in Q\) — отсюда машина стартует.
- \(F\): множество принимающих (конечных) состояний, \(F \subseteq Q\). Строка принимается, если после чтения всего входа машина оказалась в одном из этих состояний.
Детерминированность означает: для каждой пары «состояние, символ» существует ровно одно следующее состояние. В недетерминированных FSA (NFA) возможны несколько вариантов следующего состояния; здесь основной фокус — на DFA.
1.7 Чтение строки автоматом FSA
Для строки (последовательности символов) \(s = c_1c_2...c_n\) FSA обрабатывает её так:
- Старт в начальном состоянии \(q_0\)
- Читаем \(c_1\) и переходим в \(\delta(q_0, c_1)\)
- Читаем \(c_2\) и переходим в \(\delta(\delta(q_0, c_1), c_2)\)
- Продолжаем, пока не прочитаны все символы
- Если конечное состояние лежит в \(F\), строка принимается; иначе отвергается.
1.8 Расширенная функция переходов
Чтобы формализовать обработку целой строки, вводят расширенную функцию переходов \(\delta^*\):
\[\delta^*: Q \times \Sigma^* \rightarrow Q\]
Она обрабатывает всю строку (не один символ). Задаётся рекурсивно:
- База: \(\delta^*(q, \epsilon) = q\) (пустая строка не меняет состояние)
- Шаг: для любой строки \(y\) и символа \(\sigma\), \(\delta^*(q, y\sigma) = \delta(\delta^*(q, y), \sigma)\) (сначала \(y\), затем \(\sigma\))
Так формализуется пошаговый процесс из предыдущего пункта.
1.9 Принятие строк и языки
- Строка \(x\) принимается FSA \(M\), если \(\delta^*(q_0, x) \in F\)
- Строка отвергается FSA \(M\), если конечное состояние не в \(F\) (или переход не определён у неполного FSA)
- Язык, распознаваемый \(M\), обозначается \(L(M)\) — множество всех принимаемых строк: \(L(M) = \{x \in \Sigma^* \mid \delta^*(q_0, x) \in F\}\)
- Язык \(L\) называется регулярным, если существует FSA \(M\) такой, что \(L = L(M)\)
1.10 Полные и неполные FSA
- Полный FSA: \(\delta\) всюду определена: для всех \(q \in Q\) и \(\sigma \in \Sigma\) задано \(\delta(q, \sigma)\). Любую строку можно обработать без «застревания».
- Неполный FSA: \(\delta\) частичная, некоторые переходы не заданы. При попытке следовать неопределённому переходу строка отвергается (нельзя достичь принимающего состояния).
Чтобы сделать неполный FSA полным, обычно добавляют состояние‑ловушку (или ошибочное состояние): все ранее неопределённые переходы ведут в него. Ловушка не принимающая; попав в неё, автомат обычно остаётся там (часто с петлёй на все символы).
1.11 Графическое представление
FSA изображают диаграммами состояний:
- Состояния — круги (или скруглённые прямоугольники)
- Стрелка «ниоткуда» указывает на начальное состояние \(q_0\)
- Принимающие состояния — двойные круги
- Переходы — стрелки с подписями символов (или множеств символов)
- Петля — переход из состояния в себя
1.12 Детерминированные и недетерминированные FSA
- DFA: для каждой пары «состояние, символ» ровно одно следующее состояние — как в формальном определении выше.
- NFA: для пары «состояние, символ» может быть ноль, одно или несколько следующих состояний; допускаются переходы по пустой строке (\(\epsilon\)).
NFA удобнее в записях, но любой NFA эквивалентен некоторому DFA. В курсе основной упор — на детерминированные FSA.
1.13 Конечные и бесконечные языки
Конечные языки — множества из конечного числа строк. Например, \(L = \{1, 00, 0101\}\) содержит ровно три строки. Любой конечный язык регулярен и распознаётся некоторым FSA: язык можно представить бинарным деревом состояний — по ветви на каждую строку, рёбра соответствуют символам, листья, соответствующие словам из \(L\), делают принимающими. Так как язык конечен, число узлов конечно, и построение корректно.
Бесконечные языки содержат бесконечно много строк. Не все бесконечные языки регулярны, но многие — да. Два типичных регулярных бесконечных примера:
- Строки, начинающиеся с «0»: \(L = \{0w \mid w \in \{0,1\}^*\}\). Достаточно двух состояний: непринимающее начальное \(q_0\) переходит в принимающее \(q_1\) по входу \(0\), а \(q_1\) имеет петли по \(0\) и \(1\). Язык бесконечен, но регулярен.
- Язык \((ab)^k\): \(L = \{(ab)^k \mid k \geq 0\} = \{\epsilon, ab, abab, ababab, \ldots\}\). Тремя состояниями можно распознать язык: старт и приём в \(q_0\), переходы \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0\), прочие переходы — в непринимающую ловушку.
Напротив, язык \(L = \{a^k b^k \mid k \in \mathbb{N}\}\) (одинаковое число \(a\), затем столько же \(b\)) бесконечен и не регулярен. Чтобы принять его, нужно помнить точное \(k\), то есть неограниченную память. У FSA лишь конечное число состояний, произвольное \(k\) «сосчитать» нельзя — на достаточно длинных входах автомат ошибётся. Это формализуется леммой накачки для регулярных языков.
1.14 Применения в компиляторах
FSA критичны для лексического анализа — первой фазы компиляции:
- Lexer (сканер) читает исходный код посимвольно
- С помощью FSA выделяются лексемы: идентификаторы, ключевые слова, числа, операторы, пунктуация
- Идентификатор в большинстве языков начинается с буквы, за которой следует ноль или больше букв и цифр
- FSA распознаёт шаблон: начальное состояние → (буква) → принимающее → петля (буква/цифра)* → принимающее
Генератор лексеров вроде lex по регулярным выражениям (описывающим регулярные языки) автоматически строит FSA и код сканера.
1.15 Конечные преобразователи
Конечный преобразователь состояний (FST, Finite State Transducer) — расширение FSA, которое помимо принятия/отклонения входа выдаёт выход. У FST есть:
- Входная лента с символами входного алфавита
- Выходная лента, куда пишутся символы выходного алфавита
- Переходы с метками \(i/o\) (прочитали \(i\), записали \(o\))
FST применяют для:
- компиляции в целевой код
- перевода между языками
- сжатия и распаковки
- замены шаблонов в тексте
Формально FST — 7‑ка:
\[T = \langle Q, I, O, \delta, q_0, F, \eta \rangle\]
где:
- \(Q\) — конечное множество состояний
- \(I\) — конечный входной алфавит
- \(O\) — конечный выходной алфавит
- \(\delta: Q \times I \rightarrow Q\) — функция переходов по состояниям
- \(q_0 \in Q\) — начальное состояние
- \(F \subseteq Q\) — принимающие состояния
- \(\eta: Q \times I \rightarrow O^*\) — выходная функция: для пары «состояние, входной символ» задаётся строка выходных символов, выдаваемая на этом переходе
Отношение преобразования, вычисляемое \(T\), обозначают \(\tau\). Для входной строки \(x \in I^*\), если \(T\) принимает \(x\) и при обработке выдаёт строку \(y \in O^*\), пишут:
\[y = \tau(x)\]
В общем случае \(\tau \subseteq I^* \times O^*\) — отношение (не обязательно функция: недетерминированный FST может давать разные выходы на один вход). Если \(T\) детерминирован, \(\tau\) — частичная функция \(I^* \to O^*\).
1.16 Абстракция и коммуникация
Важнейший навык информатика — и в целом инженера — свободно переходить между двумя уровнями описания:
- Неформальный (интуитивный): рассказ или рисунок, передающий замысел системы без полной математической строгости. Пример: «турникет открывается, когда бросаешь монету».
- Формальный (математический): жёсткая спецификация в общепринятой нотации, однозначная и пригодная для механических рассуждений. Пример: 5‑ка \(M = (Q, \Sigma, \delta, q_0, F)\) и явная таблица переходов.
Умение переводить между уровнями — абстракция — позволяет из неформальных требований заказчика получать корректный, проверяемый код. Без абстракции идеи остаются размытыми; без опоры на формализм математические объекты отрываются от реальности.
Связь с риторическим треугольником Аристотеля. Убедительное изложение технических идей требует баланса трёх элементов:
| Элемент | Значение | В техническом контексте |
|---|---|---|
| Logos (логос) | Логическое содержание и структура аргумента | Формальное определение, доказательство, алгоритм |
| Ethos (этос) | Авторитет и доверие к говорящему | Ссылки на установленные результаты, аккуратная нотация |
| Pathos (патос) | Эмоциональная связь, учёт аудитории | Наглядные примеры, аналогии, мотивация |
Сильное техническое объяснение сочетает logos (строгий аргумент), ethos (опора на теорию) и pathos (примеры и мотивация для читателя). Понимание этого баланса помогает формулировать спецификации, проекты и доказательства для коллег, заказчиков и средств формальной верификации.
2. Определения
- Алфавит (\(\Sigma\)): конечное множество символов, из которых составляют строки.
- Строка: последовательность нуля или более символов алфавита. Пустая строка обозначается \(\epsilon\).
- Состояние: конфигурация FSA; в каждый момент автомат ровно в одном состоянии.
- Начальное состояние (\(q_0\)): состояние, с которого начинается обработка любой входной строки.
- Принимающее состояние (конечное): если после чтения всего входа FSA в таком состоянии, строка принимается. Множество принимающих состояний — \(F\).
- Функция переходов (\(\delta\)): \(\delta: Q \times \Sigma \rightarrow Q\) задаёт следующее состояние по текущему состоянию и символу. Если функция частичная, некоторые переходы не определены.
- Полный FSA: \(\delta\) определена для всех \((q, \sigma) \in Q \times \Sigma\).
- Неполный FSA: \(\delta\) определена не для всех пар; часть переходов отсутствует.
- Расширенная функция переходов (\(\delta^*\)): обобщение \(\delta\) на целые строки: \(\delta^*(q, \epsilon) = q\) и \(\delta^*(q, y\sigma) = \delta(\delta^*(q, y), \sigma)\).
- Язык: множество строк над алфавитом; может быть конечным или бесконечным.
- Регулярный язык: язык, распознаваемый некоторым конечным автоматом.
- DFA: FSA, в котором из каждого состояния по каждому символу не более одного исходящего перехода (нет недетерминизма).
- NFA: FSA, где по одному символу возможно несколько исходящих переходов или есть \(\epsilon\)‑переходы.
- Состояние‑ловушка (ошибочное): непринимающее состояние для дополнения неполного FSA до полного; все «дыры» в \(\delta\) ведут в ловушку; обычно из неё нет выхода.
- FST: FSA с выходной лентой и выходной функцией; задаёт преобразование входных строк в выходные.
- Lexer (сканер): программа, читающая текст посимвольно и с помощью FSA выделяет лексемы (идентификаторы, ключевые слова, числа и т.д.).
3. Формулы
- Функция переходов: \(\delta: Q \times \Sigma \rightarrow Q\), где \(\delta(q, \sigma)\) — следующее состояние из \(q\) по символу \(\sigma\)
- Расширенная функция (база): \(\delta^*(q, \epsilon) = q\)
- Расширенная функция (рекурсия): \(\delta^*(q, y\sigma) = \delta(\delta^*(q, y), \sigma)\)
- Принятие строки: \(x \in \Sigma^*\) принимается \(M\), если \(\delta^*(q_0, x) \in F\)
- Язык FSA: \(L(M) = \{x \in \Sigma^* \mid \delta^*(q_0, x) \in F\}\)
- Неполный автомат: \(x\) принимается, если все переходы \(q_k = \delta(q_{k-1}, c_k)\) определены для символов \(x\) и конечное состояние лежит в \(F\)
4. Примеры
4.1. Турникет: формальное описание (Лаба 3, Пример 1)
Смоделируйте турникет метро как FSA. Два состояния: Locked (Заперто) и Unlocked (Открыто). Изначально Locked. Типовая последовательность: Coin в Locked \(\rightarrow\) переход в Unlocked, затем Push \(\rightarrow\) снова Locked. Push в Locked или Coin в Unlocked не меняют состояние. Accepting state — Locked.
Показать решение
Шаг 1: компоненты
- Состояния: Заперто и Открыто
- Алфавит: {Толкнуть, Монета}
- Начальное состояние: Заперто (нормальное «закрытое» состояние)
- Принимающее состояние: Заперто (транзакция завершена корректно)
Шаг 2: переходы
- Заперто + Толкнуть → Заперто
- Заперто + Монета → Открыто
- Открыто + Толкнуть → Заперто
- Открыто + Монета → Открыто
Шаг 3: формальное определение
\[M = (Q, \Sigma, \delta, q_0, F)\]
где:
- \(Q = \{\text{Заперто}, \text{Открыто}\}\)
- \(\Sigma = \{\text{Толкнуть}, \text{Монета}\}\)
- \(\delta\) задана таблицей:
| \(\delta\) | Толкнуть | Монета |
|---|---|---|
| Заперто | Заперто | Открыто |
| Открыто | Заперто | Открыто |
- \(q_0 = \text{Заперто}\)
- \(F = \{\text{Заперто}\}\)
Шаг 4: примеры строк
- \(\epsilon\): старт в Заперто (принимающее) → ПРИНЯТЬ
- «Толкнуть–Толкнуть»: Заперто →Толкнуть→ Заперто →Толкнуть→ Заперто → ПРИНЯТЬ
- «Монета»: Заперто →Монета→ Открыто (не принимающее) → ОТВЕРГНУТЬ
- «Толкнуть–Монета–Монета–Монета–Толкнуть»: в конце Заперто → ПРИНЯТЬ
Этот FSA принимает в точности те последовательности, в которых каждая Монета когда‑то сопровождается (впоследствии) Толкнуть.
4.2. Простая задача: какую строку нельзя принять? (Лаба 3, Задание 1)
Рассмотрите FSA ниже. Какую из строк этот автомат не может принять?
Описание FSA:
- Состояния: \(s_1\) (начальное), \(s_2\), \(s_3\), \(s_4\) (принимающее)
- Переходы:
- \(s_1 \xrightarrow{a} s_2\)
- \(s_2 \xrightarrow{a} s_2\) (петля)
- \(s_2 \xrightarrow{b} s_1\)
- \(s_2 \xrightarrow{c} s_4\)
- \(s_4 \xrightarrow{d} s_3\)
- \(s_3 \xrightarrow{a} s_1\)
- \(s_3 \xrightarrow{b} s_4\)
Какие из строк отвергаются?
- «ac»
- «aaac»
- «aaacda»
- «aaacdb»
Показать решение
Ключевая идея: прослеживаем состояния по символам. Неопределённый переход — немедленный отказ. Если вход кончился не в принимающем состоянии — отказ.
Шаг 1: структура
- Из \(s_1\): только «a» → \(s_2\)
- Из \(s_2\): «a» (петля), «b» → \(s_1\), «c» → \(s_4\)
- Из \(s_3\): «a» → \(s_1\), «b» → \(s_4\)
- Из \(s_4\): только «d» → \(s_3\)
Из \(s_1\) не определены «b», «c», «d»; из \(s_4\) не определены «a», «b», «c».
Шаг 2: строка «ac»
- Старт: \(s_1\)
- «a»: \(s_1 \xrightarrow{a} s_2\)
- «c»: \(s_2 \xrightarrow{c} s_4\)
- Конец: \(s_4\) (принимающее) → ПРИНЯТЬ
Шаг 3: «aaac»
- \(s_1 \xrightarrow{a} s_2 \xrightarrow{a} s_2 \xrightarrow{a} s_2 \xrightarrow{c} s_4\) → ПРИНЯТЬ
Шаг 4: «aaacda»
- … \(s_2 \xrightarrow{c} s_4 \xrightarrow{d} s_3 \xrightarrow{a} s_1\)
- Конец: \(s_1\) (не принимающее) → ОТВЕРГНУТЬ
Шаг 5: «aaacdb»
- … \(s_3 \xrightarrow{b} s_4\) — конец в \(s_4\) → ПРИНЯТЬ
Ответ: наиболее явный отказ — (c) «aaacda» (конец в \(s_1\), не принимающем). Строку (d) «aaacdb» автомат принимает.
4.3. Двоичные числа, начинающиеся с 1 (Лаба 3, Задание 2)
Постройте полный FSA для языка: \[L_1 = \{x \in \{0, 1\}^* \mid x \text{ начинается с } 1\}\]
Примеры: «1», «10», «11», «100», «101», …
Показать решение
Ключевая идея: нужно распознать строки, у которых первый символ — 1. После первой единицы мы в принимающем состоянии; любые дальнейшие 0 и 1 сохраняют приём.
Шаг 1: состояния
- \(q_0\) (начальное): ещё ничего не прочитали; не принимаем.
- \(q_1\): уже видели хотя бы одну 1 с начала; принимаем; петли по 0 и 1.
- \(q_2\) (ловушка): первым прочитали 0 — отвергаем всё.
Шаг 2: переходы
Из \(q_0\): 0 → \(q_2\); 1 → \(q_1\).
Из \(q_1\): 0 и 1 → \(q_1\).
Из \(q_2\): 0 и 1 → \(q_2\).
Шаг 3: формальное определение
\[M_1 = (Q, \Sigma, \delta, q_0, F)\]
где \(Q = \{q_0, q_1, q_2\}\), \(\Sigma = \{0, 1\}\), \(F = \{q_1\}\), таблица:
| \(\delta\) | 0 | 1 |
|---|---|---|
| \(q_0\) | \(q_2\) | \(q_1\) |
| \(q_1\) | \(q_1\) | \(q_1\) |
| \(q_2\) | \(q_2\) | \(q_2\) |
Шаг 4: проверка
- «1», «10», «101» → ПРИНЯТЬ ✓
- «0», «01» → ОТВЕРГНУТЬ ✓
Автомат полный: из каждого состояния есть переходы по 0 и 1.
4.4. Двоичные строки, не начинающиеся с 1 (Лаба 3, Задание 3)
Постройте полный FSA для: \[L_2 = \{x \in \{0, 1\}^* \mid x \text{ не начинается с } 1\}\]
Примеры: «», «0», «00», «01», «001», …
Показать решение
Ключевая идея: язык включает пустую строку (она «не начинается с 1») и все строки, у которых первый символ 0. После первого 0 принимаем любое продолжение.
Шаг 1: состояния
- \(q_0\): вход пуст — принимаем \(\epsilon\).
- \(q_1\): первым был 0 — принимаем и дальше.
- \(q_2\): первым была 1 — ловушка.
Шаг 2–3: \(M_2\) с \(F = \{q_0, q_1\}\), таблица:
| \(\delta\) | 0 | 1 |
|---|---|---|
| \(q_0\) | \(q_1\) | \(q_2\) |
| \(q_1\) | \(q_1\) | \(q_1\) |
| \(q_2\) | \(q_2\) | \(q_2\) |
Шаг 4: «», «0», «01» → ПРИНЯТЬ; «1», «10» → ОТВЕРГНУТЬ ✓
4.5. Любая 0 сразу за которой есть хотя бы одна 1 (Лаба 3, Задание 4)
Полный FSA для: \[L_3 = \{x \in \{0, 1\}^* \mid \text{любая } 0 \text{ в } x \text{ непосредственно сопровождается хотя бы одной } 1\}\]
Примеры: «010111», «1111», «01110111011». Недопустимы 0 в конце строки и подстрока «00».
Показать решение
Ключевая идея: каждая 0 в строке должна быть непосредственно сопровождена хотя бы одной 1. Значит, запрещены: 0 в самом конце строки и пара «00» подряд.
Шаг 1: состояния
- \(q_0\) (начальное, принимающее): последний прочитанный символ — 1 или вход ещё пуст; здесь можно закончить и принять.
- \(q_1\): только что прочитали 0; следующий символ обязан быть 1.
- \(q_2\) (ловушка): либо встретили «00», либо другая фатальная ошибка.
Шаг 2: переходы
Из \(q_0\): 0 → \(q_1\); 1 → \(q_0\).
Из \(q_1\): 0 → \(q_2\); 1 → \(q_0\).
Из \(q_2\): 0 и 1 → \(q_2\).
Шаг 3: формальное определение
\[M_3 = (Q, \Sigma, \delta, q_0, F)\]
где \(Q = \{q_0, q_1, q_2\}\), \(\Sigma = \{0, 1\}\), \(F = \{q_0\}\),
| \(\delta\) | 0 | 1 |
|---|---|---|
| \(q_0\) | \(q_1\) | \(q_0\) |
| \(q_1\) | \(q_2\) | \(q_0\) |
| \(q_2\) | \(q_2\) | \(q_2\) |
Шаг 4: проверка
- «1111»: остаёмся в \(q_0\) → ПРИНЯТЬ ✓
- «010111»: \(q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{1} q_0\) → ПРИНЯТЬ ✓
- «01110111011»: аналогично заканчиваем в \(q_0\) → ПРИНЯТЬ ✓
- «10»: \(q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1\) — конец в \(q_1\) (не принимающее) → ОТВЕРГНУТЬ ✓
- «100»: \(q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2\) → ОТВЕРГНУТЬ ✓
4.6. Двоичные строки, оканчивающиеся на 00 (Лаба 3, Задание 5)
Полный FSA для: \[L_4 = \{x \in \{0, 1\}^* \mid x \text{ оканчивается на } 00\}\]
Примеры: «00», «100», «1100», «00100».
Показать решение
Ключевая идея: отслеживать, что два последних символа — оба 0. Нужны состояния: (1) на конце нет «хвоста» из нулей подряд, (2) на конце один 0, (3) на конце «00» (принимаем).
Шаг 1: состояния
- \(q_0\) (начальное): на конце нет 0 (только что прочитали 1, или вход ещё пуст, или только начали).
- \(q_1\): последний символ — 0, но предпоследний — не 0.
- \(q_2\) (принимающее): последние два символа — «00».
Шаг 2: переходы
Из \(q_0\): 0 → \(q_1\); 1 → \(q_0\).
Из \(q_1\): 0 → \(q_2\); 1 → \(q_0\).
Из \(q_2\): 0 → \(q_2\); 1 → \(q_0\).
Шаг 3: формальное определение
\[M_4 = (Q, \Sigma, \delta, q_0, F)\]
где \(Q = \{q_0, q_1, q_2\}\), \(\Sigma = \{0, 1\}\), \(F = \{q_2\}\), таблица:
| \(\delta\) | 0 | 1 |
|---|---|---|
| \(q_0\) | \(q_1\) | \(q_0\) |
| \(q_1\) | \(q_2\) | \(q_0\) |
| \(q_2\) | \(q_2\) | \(q_0\) |
Шаг 4: проверка
- «00», «100», «1100» → ПРИНЯТЬ ✓
- «101» → ОТВЕРГНУТЬ ✓
4.7. Ровно три нуля в двоичной строке (Лаба 3, Задание 6)
Полный FSA для: \[L_5 = \{x \in \{0, 1\}^* \mid x \text{ содержит ровно три нуля}\}\]
Примеры: «000», «0001», «1010100», «11001001».
Показать решение
Ключевая идея: нужно «считать» число нулей. Вводим состояния: видели 0, 1, 2, 3 нуля; больше трёх нулей — ловушка.
Шаг 1: состояния
- \(q_0\): пока не встретили ни одного 0.
- \(q_1\): ровно один 0.
- \(q_2\): ровно два нуля.
- \(q_3\) (принимающее): ровно три нуля.
- \(q_4\) (ловушка): четыре и больше нулей.
Шаг 2: переходы
Чтение 1 не меняет «счётчик» нулей (остаёмся в том же состоянии). Чтение 0 увеличивает счёт до перехода в \(q_4\).
Шаг 3: формальное определение
\[M_5 = (Q, \Sigma, \delta, q_0, F)\]
где \(Q = \{q_0, q_1, q_2, q_3, q_4\}\), \(\Sigma = \{0, 1\}\), \(F = \{q_3\}\), а \(\delta\):
| \(\delta\) | 0 | 1 |
|---|---|---|
| \(q_0\) | \(q_1\) | \(q_0\) |
| \(q_1\) | \(q_2\) | \(q_1\) |
| \(q_2\) | \(q_3\) | \(q_2\) |
| \(q_3\) | \(q_4\) | \(q_3\) |
| \(q_4\) | \(q_4\) | \(q_4\) |
Шаг 4: проверка
- «000»: \(q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_3\) → ПРИНЯТЬ ✓
- «0001»: \(q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{1} q_3\) → ПРИНЯТЬ ✓
- «1010100»: … \(\xrightarrow{0} q_4\) → ОТВЕРГНУТЬ ✓
- «11001001»: … \(\xrightarrow{0} q_4\) → ОТВЕРГНУТЬ ✓
4.8. Каждая a сразу за которой идёт bb (Лаба 3, Задание 7)
Полный FSA для: \[L_6 = \{x \in \{a, b\}^* \mid \text{каждая } a \text{ в } x \text{ непосредственно сопровождается } bb\}\]
Примеры: «», «b», «bb», «abbabb», «bbbabbb».
Показать решение
Ключевая идея: после каждой «a» должны сразу идти «b» и ещё «b» — подстрока «abb». Иные «a» допустимы только в рамках этого же правила.
Шаг 1: состояния
- \(q_0\) (начальное, принимающее): можно принять; нет незавершённого шаблона «abb».
- \(q_1\): только что прочитали «a», дальше обязательно «b».
- \(q_2\): прочитали «ab», нужна вторая «b».
- \(q_3\) (ловушка): нарушение (например, «a» не сопровождается «bb»).
Шаг 2: переходы
Из \(q_0\): «a» → \(q_1\); «b» → \(q_0\).
Из \(q_1\): «a» → \(q_3\); «b» → \(q_2\).
Из \(q_2\): «a» → \(q_3\); «b» → \(q_0\).
Из \(q_3\): «a», «b» → \(q_3\).
Шаг 3: формальное определение
\[M_6 = (Q, \Sigma, \delta, q_0, F)\]
\(Q=\{q_0,q_1,q_2,q_3\}\), \(\Sigma=\{a,b\}\), начальное состояние — \(q_0\), \(F=\{q_0\}\).
| \(\delta\) | a | b |
|---|---|---|
| \(q_0\) | \(q_1\) | \(q_0\) |
| \(q_1\) | \(q_3\) | \(q_2\) |
| \(q_2\) | \(q_3\) | \(q_0\) |
| \(q_3\) | \(q_3\) | \(q_3\) |
Шаг 4: проверка
- «», «b», «bb», «abb», «abbabb» → ПРИНЯТЬ ✓
- «ab»: конец в \(q_2\) → ОТВЕРГНУТЬ ✓
- «aba»: уход в \(q_3\) → ОТВЕРГНУТЬ ✓
4.9. Оканчивается на b и нет подстроки aa (Лаба 3, Задание 8)
\[L_7 = \{x \in \{a, b\}^* \mid x \text{ оканчивается на } b \text{ и не содержит подстроки } aa\}\]
Примеры: «b», «ab», «bab», «abb», «abab», «babab». Не подходят: «a», «aa», «baa», «aba» (конец «a»), «aab» (есть «aa»).
Показать решение
Ключевая идея: выполнить одновременно два условия: (1) подстроки «aa» нигде нет; (2) строка заканчивается на «b». Отслеживаем: только что видели «a» или «b»; при появлении «aa» уходим в ловушку.
Шаг 1: состояния
- \(q_0\) (начальное): последний прочитанный символ — «b», или мы в самом начале; если вход кончился здесь и мы не нарушали правила, можно принять.
- \(q_1\): последний символ — «a», при этом перед ним не было второй «a» подряд.
- \(q_2\) (ловушка): встретили «aa» или дальше уже не выйти к корректному концу.
Принимающее только \(q_0\) (последний символ строки — «b»).
Шаг 2: переходы
Из \(q_0\): «a» → \(q_1\); «b» → \(q_0\).
Из \(q_1\): «a» → \(q_2\); «b» → \(q_0\).
Из \(q_2\): «a», «b» → \(q_2\).
Шаг 3: формальное определение
\[M_7 = (Q, \Sigma, \delta, q_0, F),\quad Q=\{q_0,q_1,q_2\},\ \Sigma=\{a,b\},\ F=\{q_0\}\]
| \(\delta\) | a | b |
|---|---|---|
| \(q_0\) | \(q_1\) | \(q_0\) |
| \(q_1\) | \(q_2\) | \(q_0\) |
| \(q_2\) | \(q_2\) | \(q_2\) |
Шаг 4: проверка
- «b», «ab», «bab», «abb», «abab» → ПРИНЯТЬ ✓
- «a», «aa», «aab», «aba» → ОТВЕРГНУТЬ ✓
4.10. Содержит подстроку abbaab (Лаба 3, Задание 9)
\[L_8 = \{x \in \{a, b\}^* \mid x \text{ содержит подстроку } abbaab\}\]
Примеры: «abbaab», «aabbaab», «ababbaab».
Показать решение
Ключевая идея: накапливать совпадение с префиксом «abbaab». При «срыве» нужно корректно откатываться к подходящему префиксу. После полного совпадения остаёмся в принимающем состоянии при любых дальнейших символах.
Шаг 1: состояния
- \(q_0\): префикс «abbaab» ещё не начат.
- \(q_1\): совпал префикс «a».
- \(q_2\): «ab».
- \(q_3\): «abb».
- \(q_4\): «abba».
- \(q_5\): «abbaa».
- \(q_6\) (принимающее): «abbaab»; дальше петли на все символы.
Шаг 2: переходы (суть)
Из \(q_0\): «a» → \(q_1\); «b» → \(q_0\).
Из \(q_1\): «a» → \(q_1\); «b» → \(q_2\).
Из \(q_2\): «a» → \(q_1\); «b» → \(q_3\).
Из \(q_3\): «a» → \(q_4\); «b» → \(q_3\).
Из \(q_4\): «a» → \(q_5\); «b» → \(q_0\).
Из \(q_5\): «a» → \(q_1\); «b» → \(q_6\).
Из \(q_6\): «a», «b» → \(q_6\).
Шаг 3: таблица \(\delta\)
| \(\delta\) | a | b |
|---|---|---|
| \(q_0\) | \(q_1\) | \(q_0\) |
| \(q_1\) | \(q_1\) | \(q_2\) |
| \(q_2\) | \(q_1\) | \(q_3\) |
| \(q_3\) | \(q_4\) | \(q_3\) |
| \(q_4\) | \(q_5\) | \(q_0\) |
| \(q_5\) | \(q_1\) | \(q_6\) |
| \(q_6\) | \(q_6\) | \(q_6\) |
Шаг 4: проверка
- «abbaab»: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{b} q_3 \xrightarrow{a} q_4 \xrightarrow{a} q_5 \xrightarrow{b} q_6\) → ПРИНЯТЬ ✓
- «aabbaab»: через \(q_1\) дважды по «a», затем как выше → ПРИНЯТЬ ✓
4.11. Чётное число a и чётное число b (Лаба 3, Задание 10)
\[L_9 = \{x \in \{a, b\}^* \mid x \text{ содержит чётное число символов } a \text{ и чётное число символов } b\}\]
Примеры: «», «aabb», «abab», «aabbab», «baba» (по две «a» и две «b»).
Показать решение
Ключевая идея: независимо отслеживать чётность счётчиков «a» и «b» — четыре комбинации чёт/нечёт.
Шаг 1: состояния
- \(q_{00}\) (начальное и принимающее): чётное число «a», чётное число «b».
- \(q_{01}\): чётное «a», нечётное «b».
- \(q_{10}\): нечётное «a», чётное «b».
- \(q_{11}\): нечётное «a», нечётное «b».
Шаг 2: переходы
Каждая «a» меняет чётность «a»; каждая «b» — чётность «b».
Из \(q_{00}\): «a» → \(q_{10}\); «b» → \(q_{01}\).
Из \(q_{01}\): «a» → \(q_{11}\); «b» → \(q_{00}\).
Из \(q_{10}\): «a» → \(q_{00}\); «b» → \(q_{11}\).
Из \(q_{11}\): «a» → \(q_{01}\); «b» → \(q_{10}\).
Шаг 3: формальное определение
\[M_9 = (Q, \Sigma, \delta, q_0, F),\quad Q=\{q_{00},q_{01},q_{10},q_{11}\},\ \Sigma=\{a,b\},\ q_0=q_{00},\ F=\{q_{00}\}\]
| \(\delta\) | a | b |
|---|---|---|
| \(q_{00}\) | \(q_{10}\) | \(q_{01}\) |
| \(q_{01}\) | \(q_{11}\) | \(q_{00}\) |
| \(q_{10}\) | \(q_{00}\) | \(q_{11}\) |
| \(q_{11}\) | \(q_{01}\) | \(q_{10}\) |
Шаг 4: проверка
- «»: в \(q_{00}\) → ПРИНЯТЬ ✓
- «aabb», «abab» → ПРИНЯТЬ ✓
- «a», «aab» → ОТВЕРГНУТЬ ✓
4.12. Двоичная запись, делимость на 5, начинается с 1 (Лаба 3, Задание 11)
\[L_{10} = \{x \in \{0, 1\}^* \mid x \text{ — двоичная запись целого, делящегося на } 5,\ \text{и первая цифра } 1\}\]
Примеры: «101» (5), «1010» (10), «1111» (15), «11001» (25).
Показать решение
Ключевая идея: число делится на 5 тогда и только тогда, когда остаток по модулю 5 равен 0. Читая биты слева направо, обновляем остаток: если сейчас остаток \(r\), прочитали бит \(b\), то новый остаток \((2r+b)\bmod 5\).
Шаг 1: состояния
- \(q_0\) (начальное): ещё не прочитали значащих битов; не принимаем (нужна хотя бы одна «1»).
- \(q_1,\ldots,q_4\): текущий остаток \(1,2,3,4\) по мод 5.
- \(q_5\) (принимающее): остаток 0 по мод 5.
- \(q_6\) (ловушка): строка началась с 0.
Шаг 2: переходы
Для состояний с остатком \(i\) и бита \(b\): переход в \(q_{(2i+b)\bmod 5}\) (с учётом переименования: \(q_5\) соответствует остатку 0).
Из \(q_0\): 0 → \(q_6\); 1 → \(q_1\).
Из \(q_1\): 0 → \(q_2\); 1 → \(q_3\).
Из \(q_2\): 0 → \(q_4\); 1 → \(q_5\).
Из \(q_3\): 0 → \(q_1\); 1 → \(q_2\).
Из \(q_4\): 0 → \(q_3\); 1 → \(q_4\).
Из \(q_5\): 0 → \(q_5\); 1 → \(q_1\).
Из \(q_6\): 0,1 → \(q_6\).
Шаг 3: формальное определение
\[M_{10} = (Q, \Sigma, \delta, q_0, F)\]
\(Q = \{q_0, q_1, q_2, q_3, q_4, q_5, q_6\}\), \(\Sigma = \{0, 1\}\), начальное состояние — \(q_0\), \(F = \{q_5\}\).
| \(\delta\) | 0 | 1 |
|---|---|---|
| \(q_0\) | \(q_6\) | \(q_1\) |
| \(q_1\) | \(q_2\) | \(q_3\) |
| \(q_2\) | \(q_4\) | \(q_5\) |
| \(q_3\) | \(q_1\) | \(q_2\) |
| \(q_4\) | \(q_3\) | \(q_4\) |
| \(q_5\) | \(q_5\) | \(q_1\) |
| \(q_6\) | \(q_6\) | \(q_6\) |
Шаг 4: проверка
- «101» (5): \(q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_5\) → ПРИНЯТЬ ✓
- «1010» (10), «1111» (15) → ПРИНЯТЬ ✓
- «1100» (12) → ОТВЕРГНУТЬ ✓
4.13. Длина ≥ 2 и два последних символа совпадают (Лаба 3, Задание 12)
\[L_{11} = \{x \in \{0, 1\}^* \mid |x| \geq 2 \wedge \text{ два последних символа совпадают}\}\]
Примеры: «00», «11», «100», «011», «0100».
Показать решение
Ключевая идея: хранить последние два символа и обеспечить \(|x|\geq 2\). Сначала удобно различить длину 1: после первого символа нужно знать, был ли он 0 или 1.
Шаг 1 (черновик): \(q_0\) — ничего не прочитали; \(q_1\) — один символ; затем состояния для пар «00», «01», «10», «11».
Шаг 1 (уточнение):
- \(q_0\) (начальное): вход пуст.
- \(q_{1a}\): прочитан ровно один символ «0».
- \(q_{1b}\): прочитан ровно один символ «1».
- \(q_2\) (принимающее): суффикс «00».
- \(q_3\): суффикс «01».
- \(q_4\): суффикс «10».
- \(q_5\) (принимающее): суффикс «11».
Шаг 2: переходы
Из \(q_0\): 0 → \(q_{1a}\); 1 → \(q_{1b}\).
Из \(q_{1a}\): 0 → \(q_2\); 1 → \(q_3\).
Из \(q_{1b}\): 0 → \(q_4\); 1 → \(q_5\).
Из \(q_2\): 0 → \(q_2\); 1 → \(q_3\).
Из \(q_3\): 0 → \(q_4\); 1 → \(q_5\).
Из \(q_4\): 0 → \(q_2\); 1 → \(q_3\).
Из \(q_5\): 0 → \(q_4\); 1 → \(q_5\).
Шаг 3: формальное определение
\[M_{11} = (Q, \Sigma, \delta, q_0, F)\]
\(Q = \{q_0, q_{1a}, q_{1b}, q_2, q_3, q_4, q_5\}\), \(\Sigma = \{0, 1\}\), \(F = \{q_2, q_5\}\).
| \(\delta\) | 0 | 1 |
|---|---|---|
| \(q_0\) | \(q_{1a}\) | \(q_{1b}\) |
| \(q_{1a}\) | \(q_2\) | \(q_3\) |
| \(q_{1b}\) | \(q_4\) | \(q_5\) |
| \(q_2\) | \(q_2\) | \(q_3\) |
| \(q_3\) | \(q_4\) | \(q_5\) |
| \(q_4\) | \(q_2\) | \(q_3\) |
| \(q_5\) | \(q_4\) | \(q_5\) |
Шаг 4: проверка
- «00», «11», «100», «0100» → ПРИНЯТЬ ✓
- «01», «0» → ОТВЕРГНУТЬ ✓
4.14. Подстрока abc встречается нечётное число раз (Лаба 3, Задание 13)
\[L_{12} = \{x \in \{a, b, c\}^* \mid \text{подстрока } abc \text{ в } x \text{ встречается нечётное число раз}\}\]
Показать решение
Ключевая идея: отдельно хранить чётность уже завершённых «abc» и длину текущего префикса «abc» (0, 1 или 2 символа). Завершение «abc» меняет чётность и сбрасывает прогресс.
Шаг 1: состояния \((s,p)\): \(s\in\{E,O\}\) (чётное/нечётное число полных «abc»), \(p\in\{0,1,2\}\) — сколько символов префикса «abc» уже совпало. Обозначения: \(E0,E1,E2,O0,O1,O2\).
Шаг 2: формальное определение
\[M_{12} = (\{E0, E1, E2, O0, O1, O2\},\ \{a, b, c\},\ \delta,\ E0,\ \{O0\})\]
| \(\delta\) | a | b | c |
|---|---|---|---|
| \(E0\) | \(E1\) | \(E0\) | \(E0\) |
| \(E1\) | \(E1\) | \(E2\) | \(E0\) |
| \(E2\) | \(E1\) | \(E0\) | \(O0\) |
| \(O0\) | \(O1\) | \(O0\) | \(O0\) |
| \(O1\) | \(O1\) | \(O2\) | \(O0\) |
| \(O2\) | \(O1\) | \(O0\) | \(E0\) |
Шаг 3: проверка
- «abc»: \(E0 \xrightarrow{a} E1 \xrightarrow{b} E2 \xrightarrow{c} O0\) → ПРИНЯТЬ ✓
- «abcabc»: после второго «abc» возвращаемся в \(E0\) → ОТВЕРГНУТЬ ✓
- «abcabcabc»: три раза → снова \(O0\) → ПРИНЯТЬ ✓
- \(\epsilon\): в \(E0\) (не принимающее) → ОТВЕРГНУТЬ ✓
4.15. Шариковая игрушка как FSA (Лаба 3, Домашнее задание 1)
Смоделируйте игрушку со шариком как полный FSA. Два входа (A и B), два выхода (C и D). Три рычага X1, X2, X3:
- шарик входит в A или B;
- X1 под A, X3 под B, X2 в центре;
- каждый рычаг при проходе шарика переворачивается для следующего;
- принятие — выход в D (выход в C — отказ).
Показать решение
Ключевая идея: у каждого рычага два положения (лево/право); шарик отклоняется в сторону, зависящую от положения; после прохода рычаг меняет сторону. Состояние системы — вектор из трёх положений.
Шаг 1: траектории
- Из A шарик попадает на X1. Если X1 в положении L — уходит в C; если R — идёт к X2.
- Из B шарик попадает на X3. Если X3 в L — идёт к X2; если R — сразу в D.
- С X2: L → C, R → D.
Каждый рычаг, через который прошёл шарик, переворачивается.
Шаг 2: состояния \((s_1,s_2,s_3)\), \(s_i\in\{L,R\}\). Всего \(2^3=8\) состояний. Начальное — \((L,L,L)\).
Шаг 3–5: переходы по A и B (см. пошаговый разбор в англ. лекции): из каждой тройки и входа A или B однозначно получаем новую тройку и выход C/D; \(\delta\) записывает только новое состояние после шага, а принимающие состояния — те, в которых оказались после шага с выходом в D.
Шаг 6–7: формальное определение
\[M_{\text{marble}} = (Q, \Sigma, \delta, q_0, F)\]
- \(Q = \{(L,L,L), (R,L,L), (L,R,L), (R,R,L), (L,L,R), (R,L,R), (L,R,R), (R,R,R)\}\)
- \(\Sigma = \{A, B\}\)
- \(\delta\):
| \(\delta\) | A | B |
|---|---|---|
| \((L,L,L)\) | \((R,L,L)\) | \((L,R,R)\) |
| \((R,L,L)\) | \((L,R,L)\) | \((R,R,R)\) |
| \((L,R,L)\) | \((R,R,L)\) | \((L,L,R)\) |
| \((R,R,L)\) | \((L,L,L)\) | \((R,L,R)\) |
| \((L,L,R)\) | \((R,L,R)\) | \((L,L,L)\) |
| \((R,L,R)\) | \((L,R,R)\) | \((R,L,L)\) |
| \((L,R,R)\) | \((R,R,R)\) | \((L,R,L)\) |
| \((R,R,R)\) | \((L,R,R)\) | \((R,R,L)\) |
- \(q_0 = (L,L,L)\) (до первого шага формально не принимаем по условию «мрамор вышел в D»)
- \(F = \{(L,L,L), (L,L,R), (R,L,R), (L,R,R), (R,R,R)\}\)
Шаг 8: примеры
- «A»: \((L,L,L) \xrightarrow{A} (R,L,L)\) — состояние непринимающее → ОТВЕРГНУТЬ ✓
- «AB»: \((L,L,L) \xrightarrow{A} (R,L,L) \xrightarrow{B} (R,R,R)\) → ПРИНЯТЬ ✓
- «BA»: \((L,L,L) \xrightarrow{B} (L,R,R) \xrightarrow{A} (R,R,R)\) → ПРИНЯТЬ ✓
4.16. Выключатель света (Лекция 3, Пример 1)
FSA переключателя: щелчок чередует состояния Вкл и Выкл.
Показать решение
Ключевая идея: два состояния и чередование по входу «переключить».
- \(Q = \{\text{Вкл}, \text{Выкл}\}\), \(\Sigma = \{\text{T}\}\) (toggle), \(q_0 = \text{Выкл}\), \(F=\{\text{Вкл}\}\).
- Вкл + T → Выкл; Выкл + T → Вкл.
- \[M = (\{\text{Вкл}, \text{Выкл}\}, \{\text{T}\}, \delta, \text{Выкл}, \{\text{Вкл}\})\]
Проверка: «T» → ПРИНЯТЬ; «TT» → ОТВЕРГНУТЬ; «TTT» → ПРИНЯТЬ — принимается нечётное число переключений.
4.17. ИИ в игре: призрак Pac-Man (Лекция 3, Пример 2)
Показать решение
Ключевая идея: режимы поведения как состояния FSA.
- Состояния: Блуждание; Преследование; Бегство (после энерджайзера); Возврат на базу.
- Переходы (события): Блуждание → Преследование: «заметил Pac-Man»; Преследование → Бегство: «Pac-Man съел энерджайзер»; Бегство → Блуждание: «энерджайзер кончился»; Преследование → Возврат: «съеден Pac-Man»; Возврат → Блуждание: «достигнут центр базы».
- Начальное: Блуждание. Принимающие зависят от дизайна игры.
Ответ: FSA из четырёх состояний с событийными переходами; в реальных играх логика сложнее, но идея конечных состояний та же.
4.18. Компилятор: идентификатор Pascal (Лекция 3, Пример 3)
FSA для идентификаторов Pascal: первая — буква, далее ноль или больше букв/цифр.
Показать решение
Состояния \(q_0\), принимающее \(q_1\), ловушка \(q_E\); переходы по классам <буква>, <цифра>, <прочее> как в 3.qmd, §4.18.
\[M_{\text{Pascal ID}} = (\{q_0, q_1, q_E\}, \Sigma, \delta, q_0, \{q_1\})\]
«count», «var123» → ПРИНЯТЬ; «123var» → ОТВЕРГНУТЬ ✓
4.19. Простой FSA: распознаёт только «ba» (Туториал 3, Пример 1)
Постройте FSA, принимающий только строку «ba».
Показать решение
Ключевая идея: цепочка состояний по позициям целевой строки.
- Состояния: \(q_0\) (начальное), \(q_1\) (прочитали «b»), \(q_2\) (принимающее, прочитали «ba»).
- Переходы: \(q_0 \xrightarrow{b} q_1\), \(q_1 \xrightarrow{a} q_2\); все остальные переходы не заданы (неполный FSA).
- Проверка: «ba» → ПРИНЯТЬ ✓; «ab»: из \(q_0\) по «a» перехода нет → ОТВЕРГНУТЬ ✓
Ответ: три состояния и линейный путь \(q_0 \to q_1 \to q_2\), задающий строку «ba».
4.20. Простой FSA: распознаёт только «aba» (Туториал 3, Пример 2)
Показать решение
Ключевая идея: как в примере 4.19, по одному состоянию на каждый прочитанный префикс.
- Состояния: \(q_0\), \(q_1\) (после «a»), \(q_2\) (после «ab»), \(q_3\) (принимающее, после «aba»).
- Переходы: \(q_0 \xrightarrow{a} q_1\), \(q_1 \xrightarrow{b} q_2\), \(q_2 \xrightarrow{a} q_3\).
- Проверка: «aba» → ПРИНЯТЬ ✓
Ответ: четыре состояния в линейной цепочке «aba».
4.21. Полный FSA для «ba» с ловушкой (Туториал 3, Пример 3)
Дополните автомат для «ba» до полного, добавив ловушку.
Показать решение
Ключевая идея: все ранее неопределённые переходы направить в новое непринимающее состояние \(q_3\).
- Исходно: \(q_0 \xrightarrow{b} q_1\), \(q_1 \xrightarrow{a} q_2\) (принимающее).
- Добавляем \(q_3\): из \(q_0\) по «a» → \(q_3\); из \(q_1\) по «b» → \(q_3\); из \(q_2\) по «a» и «b» → \(q_3\); из \(q_3\) петли по «a» и «b».
- Каждое состояние имеет исходящие переходы по всем символам алфавита \(\{a,b\}\).
Ответ: четыре состояния, \(q_3\) — ловушка для всех ошибочных продолжений.
4.22. Полный FSA для «aba» с ловушкой (Туториал 3, Пример 4)
Показать решение
Ключевая идея: та же схема, состояние‑ловушка \(q_4\).
- Из \(q_0\): «a» → \(q_1\), «b» → \(q_4\).
- Из \(q_1\): «b» → \(q_2\), «a» → \(q_4\).
- Из \(q_2\): «a» → \(q_3\), «b» → \(q_4\).
- Из \(q_3\) (принимающее): любой символ → \(q_4\), если хотим полноту после полного совпадения.
- Из \(q_4\): петли на «a», «b».
Ответ: пять состояний: \(q_0,\ldots,q_3\) и ловушка \(q_4\).
4.23. FSA с несколькими принимающими: \(L=\{a, aba\}\) (Туториал 3, Пример 5)
Показать решение
Ключевая идея: отдельное принимающее состояние для каждой допустимой строки (или общая структура с двумя «успехами»).
- Состояния: \(q_0\); \(q_1\) (принимающее, прочитали «a»); \(q_2\) (после «ab»); \(q_3\) (принимающее, после «aba»).
- Переходы: \(q_0 \xrightarrow{a} q_1\); \(q_1 \xrightarrow{b} q_2\); \(q_2 \xrightarrow{a} q_3\); для полного FSA остальное — в ловушку.
- \(F=\{q_1,q_3\}\).
Проверка: «a» и «aba» → ПРИНЯТЬ; «ab» → ОТВЕРГНУТЬ ✓
4.24. Язык с пустой строкой: \(L=\{\epsilon, ba\}\) (Туториал 3, Пример 6)
Показать решение
Ключевая идея: сделать начальное состояние принимающим, чтобы принять \(\epsilon\).
- \(q_0\) — начальное и принимающее; \(q_1\) после «b»; \(q_2\) принимающее после «ba».
- \(q_0 \xrightarrow{b} q_1\), \(q_1 \xrightarrow{a} q_2\).
- \(F=\{q_0,q_2\}\).
Проверка: \(\epsilon\) → ПРИНЯТЬ; «ba» → ПРИНЯТЬ; «b» → ОТВЕРГНУТЬ ✓
4.25. FSA, принимающий все строки над \(\{0,1\}\) (Туториал 3, Пример 7)
Показать решение
Ключевая идея: одно принимающее состояние с петлями на все символы.
- Одно состояние \(q_0\) — начальное и принимающее.
- \(q_0 \xrightarrow{0} q_0\), \(q_0 \xrightarrow{1} q_0\).
- \(F=\{q_0\}\), язык \(L=\Sigma^*\).
Поскольку \(q_0\) и начальное, и принимающее, \(\epsilon\) принимается; любая строка оставляет автомат в \(q_0\).
4.26. FSA для пустого языка (Туториал 3, Пример 8)
Показать решение
Ключевая идея: ни одно принимающее состояние недостижимо из начального (или \(F=\emptyset\)).
- Например, \(q_0\) непринимающее с петлями по 0 и 1; отдельное \(q_1\) принимающее, но без входящих рёбер.
- Ни для какой строки конечное состояние не лежит в \(F\).
Ответ: начальное непринимающее, принимающие недостижимы.
4.27. Бесконечный регулярный язык: строки, начинающиеся с 0 (Туториал 3, Пример 9)
Постройте FSA для \(L = \{w \in \{0, 1\}^* : w \text{ начинается с } 0\}\).
Показать решение
Ключевая идея: после проверки первого символа «всё остальное» остаётся в принимающем состоянии — язык бесконечен, но регулярен.
- \(q_0\) — ещё не видели первый символ; \(q_1\) — принимающее (первая цифра была 0); \(q_2\) — ловушка (первая цифра 1).
- Из \(q_0\): 0 → \(q_1\), 1 → \(q_2\). Из \(q_1\): 0,1 → \(q_1\). Из \(q_2\): 0,1 → \(q_2\).
Проверка: «0», «01101» → ПРИНЯТЬ; «1000» → ОТВЕРГНУТЬ ✓
Ответ: три состояния; после первого нуля остаёмся в принимающем навсегда.
4.28. Язык повторений «ab» (Туториал 3, Пример 10)
Постройте FSA для \(L = \{(ab)^k : k \in \mathbb{N}\} = \{\epsilon, ab, abab, ababab, \ldots\}\).
Показать решение
Ключевая идея: чередование «a» и «b»; после полной пары «ab» возврат в принимающее \(q_0\).
- \(q_0\) — начальное и принимающее (ноль или больше полных «ab»); \(q_1\) — только что прочитали «a», ждём «b»; \(q_2\) — ловушка.
- Из \(q_0\): «a» → \(q_1\), «b» → \(q_2\). Из \(q_1\): «b» → \(q_0\), «a» → \(q_2\). Из \(q_2\): петли.
Проверка: \(\epsilon\), «ab», «abab» → ПРИНЯТЬ; «aba» → ОТВЕРГНУТЬ ✓
4.29. Нерегулярные языки (Туториал 3, Пример 11)
Важная мысль: не всякий бесконечный язык регулярен. Рассмотрим \(L = \{a^k b^k : k \in \mathbb{N}\}\).
Показать решение
Ключевая идея: язык требует счёта с неограниченным запасом значений; конечной памяти FSA недостаточно.
\[L = \{a^k b^k : k \in \mathbb{N}\} = \{\epsilon, ab, aabb, aaabbb, \ldots\}\]
Почему не FSA:
- Конечное число состояний — конечный «объём памяти».
- Чтобы проверить \(a^k b^k\), нужно помнить \(k\) без верхней границы.
- Pigeonhole principle: после \(n+1\) символов «a» для автомата с \(n\) states два разных префикса попадут в одно состояние — различить разные \(k\) невозможно.
Ответ: язык не регулярен; нужны более сильные модели — PDA (магазинная память) или машина Тьюринга.